High-performance packet classification algorithms have been widely studied during the\npast decade. Bit-Vector-based algorithms proposed for FPGA can achieve very high throughput by\ndecomposing rules delicately. However, the relatively large memory resources consumption severely\nhinders applications of the algorithms extensively. It is noteworthy that, in the Bit-Vector-based\nalgorithms, stringent memory resources in FPGA are wasted to store relatively plenty of useless\nwildcards in the rules. We thus present a memory-optimized packet classification scheme named\nWeeBV to eliminate the memory occupied by the wildcards. WeeBV consists of a heterogeneous\ntwo-dimensional lookup pipeline and an optimized heuristic algorithm for searching all the wildcard\npositions that can be removed. It can achieve a significant reduction in memory resources without\ncompromising the high throughput of the original Bit-Vector-based algorithms. We implementWeeBV\nand evaluate its performance by simulation and FPGA prototype. Experimental results show that\nour approach can save 37% and 41% memory consumption on average for synthetic 5-tuple rules and\nOpenFlow rules respectively.
Loading....